{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1、二叉树查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " 算法简介\n",
    "\n",
    "        二叉查找树是先对待查找的数据进行生成树，确保树的左分支的值小于右分支的值，然后在就行和每个节点的父节点比较大小，查找最适合的范围。 这个算法的查找效率很高，但是如果使用这种查找方法要首先创建树。 \n",
    "          算法思想\n",
    "      二叉查找树（BinarySearch Tree）或者是一棵空树，或者是具有下列性质的二叉树：\n",
    "          1）若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；\n",
    "          2）若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；\n",
    "          3）任意节点的左、右子树也分别为二叉查找树。\n",
    "      二叉查找树性质：对二叉查找树进行中序遍历，即可得到有序的数列。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###  复杂度分析 \n",
    "\n",
    "         它和二分查找一样，插入和查找的时间复杂度均为O(logn)，但是在最坏的情况下仍然会有O(n)的时间复杂度。原因在于插入和删除元素的时候，树没有保持平衡。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class BSTNode:\n",
    "    \"\"\"节点\"\"\"\n",
    "    def __init__(self, data, left = None, right = None):\n",
    "        self.data = data\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        \n",
    "class BinarySortTree:\n",
    "    \"\"\"二叉查找树\"\"\"\n",
    "    def __init__(self):\n",
    "        self._root = None\n",
    "    \n",
    "    def is_empty(self):\n",
    "        return self._root is None\n",
    "    \n",
    "    def search(self, key):\n",
    "        \"\"\"\n",
    "        关键码检索\n",
    "            :param key: 关键码\n",
    "            :return: 查询节点或None\n",
    "        \"\"\"\n",
    "        bt = self._root\n",
    "        while bt:\n",
    "            entry = bt.data\n",
    "            if key < entry:\n",
    "                bt = bt.left\n",
    "            elif key > entry:\n",
    "                bt = bt.right\n",
    "            else:\n",
    "                return bt\n",
    "        return None\n",
    "    \n",
    "    def insert(self, key):\n",
    "        bt = self._root\n",
    "        if not bt:\n",
    "            self._root = BSTNode(key)\n",
    "            return\n",
    "        \n",
    "        while True:\n",
    "            entry = bt.data\n",
    "            if key < entry:\n",
    "                if not bt.left:\n",
    "                    bt.left = BSTNode(key)\n",
    "                    return \n",
    "                bt = bt.left\n",
    "            elif key > entry:\n",
    "                if not bt.right:\n",
    "                    bt.right = BSTNode(key)\n",
    "                    return \n",
    "                bt = bt.right\n",
    "            else:\n",
    "                bt.data = key\n",
    "                return\n",
    "            \n",
    "    def delete(self, key):\n",
    "        p, q = None, self._root\n",
    "        if not q:\n",
    "            # 空树\n",
    "            return\n",
    "        \n",
    "        # 先找\n",
    "        while q and q.data != key:\n",
    "            p = q\n",
    "            if key < q.data:\n",
    "                q = q.left\n",
    "            else:\n",
    "                q = q.right\n",
    "            if not q:\n",
    "                # 没找到，返回\n",
    "                return\n",
    "        # 找到了\n",
    "        if not q.left:  # 只有右节点\n",
    "            if p is None:  # q为根节点时\n",
    "                self._root = q.right\n",
    "            elif q is p.left: # q是p的左节点\n",
    "                p.left = q.right\n",
    "            else:\n",
    "                p.right = q.right # q是p的右节点\n",
    "        elif not q.right: # 只有左节点\n",
    "            if p is None:  # q为根节点时\n",
    "                self._root = q.left\n",
    "            elif q is p.left: # q是p的左节点\n",
    "                p.left = q.left\n",
    "            else:\n",
    "                p.right = q.left # q是p的右节点\n",
    "                \n",
    "        # 如果节点有两个儿子，则将其右子树的最小数据代替此节点的数据，并将其右子树的最小数据删除\n",
    "        \n",
    "        else: # 左右子树均不为空\n",
    "            r = q.right\n",
    "            if r.left is None: # 无左\n",
    "                if p is None: # 要删除的是根节点\n",
    "                    self._root = r\n",
    "                    r.left = q.left\n",
    "                else:\n",
    "                    p.left = r\n",
    "                    r.left = q.left\n",
    "            else:\n",
    "                # 左边找最小值，怎么找，一直从左边找，知道某个节点无左即可\n",
    "                n = r.left\n",
    "                while n.left:\n",
    "                    r = n\n",
    "                    n = n.left\n",
    "                # 找到了 n\n",
    "                if n.right: # n 有右子节点\n",
    "                    r.left = n.right  # r是n的爸爸\n",
    "                else: # 啥也没有\n",
    "                    r.left = None # 指向空\n",
    "                    n.left = q.left\n",
    "                    n.right = q.right\n",
    "        \n",
    "    def __iter__(self):\n",
    "        \"\"\"实现二叉树的中序遍历算法,直接使用python内置的列表作为一个栈。\"\"\"\n",
    "        stack = []\n",
    "        node = self._root\n",
    "        while node or stack:\n",
    "            while node:\n",
    "                stack.append(node)\n",
    "                node = node.left\n",
    "            node = stack.pop()\n",
    "            yield node.data  # 把node.data 暂存起来，合并作为一个迭代器。\n",
    "            node = node.right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# lis = [62, 58, 88, 48, 73, 99, 35, 51, 93, 29, 37, 49, 56, 36, 50]\n",
    "# lis = [2,5,17,11,9,7,8,16,29,35,38]\n",
    "lis = [1,2,3,4,5,6,7]\n",
    "bs_tree = BinarySortTree()\n",
    "for i in range(len(lis)):\n",
    "    bs_tree.insert(lis[i])\n",
    "# bs_tree.insert(100)\n",
    "bs_tree.delete(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 4 6 7 "
     ]
    }
   ],
   "source": [
    "for i in bs_tree:\n",
    "    print(i, end=\" \")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "7\n",
      "8\n",
      "9\n",
      "11\n",
      "16\n",
      "17\n",
      "29\n",
      "35\n",
      "38\n"
     ]
    }
   ],
   "source": [
    "def inOrderTraverse(node):\n",
    "    if node is not None:\n",
    "        inOrderTraverse(node.left)\n",
    "        print(node.data)\n",
    "        inOrderTraverse(node.right)\n",
    "inOrderTraverse(bs_tree._root)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "       如果节点有两个儿子，则将其右子树的最小数据代替此节点的数据，并将其右子树的最小数据删除\n",
    "<img src=\"二叉查找树.png\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "--\n",
      "done\n"
     ]
    }
   ],
   "source": [
    "s = [1]\n",
    "while s:\n",
    "    print('--')\n",
    "    break\n",
    "print('done')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "done\n"
     ]
    }
   ],
   "source": [
    "s = []\n",
    "while s:\n",
    "    print('--')\n",
    "    break\n",
    "print('done')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### 前序遍历\n",
    "\n",
    "    1. 前序遍历：树根->左子树->右子树\n",
    "    例如下图中二叉树前序遍历节点访问顺序为ABDGHCEIF：\n",
    "<img src=\"前序遍历.jfif\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 中序遍历\n",
    "\n",
    "    中序遍历：左子树->树根->右子树\n",
    "    例如前图中二叉树中序遍历节点访问顺序为GDHBAEICF： \n",
    "<img src=\"中序遍历.jfif\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 后序遍历\n",
    "\n",
    "    后序遍历：左子树->右子树->树根\n",
    "    例如前图中二叉树后序遍历节点访问顺序为GHDBIEFCA： \n",
    " <img src=\"后序遍历.jfif\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
